So-called artificial intelligence or pattern-matching programming has been developing and used over the last several years, such as the RETE taught by Forgy. The RETE network is one of several approaches to pattern-matching using set(s) of matching rules. These programs are well known, see the description by Charles L. Forgy in "RETE: A Fast Algorithm for the Many Pattern/Many Object Pattern Match Problem", ARTIFICIAL INTELLIGENCE, Volume 19, 1982, pp 17-37. Another example of the public knowledge in this area is found in an article by Marshall I. Schor et al in "Advances in RETE Pattern Matching", PROCEEDINGS of 1986 AMERICAN ASSOCIATION for ARTIFICIAL INTELLIGENCE CONFERENCE, pp 226-232, 1986. The well known information about RETE networks and artificial intelligence programming is not repeated herein except as needed for one of ordinary skill in this art to understand the present invention.
As is well known, such pattern-matching programming executes with a plurality of data structures. A working memory element (WME) is an input data structure. Any new WME, changed WME or deleted WME results in a "delta" requiring that the RETE be updated. The delta means that the informational content of the RETE does not reflect the WME addition, change or deletion; therefore, the RETE needs to be updated such that it reflects the current informational state of the inputs. In updating the RETE, such "delta" is represented by a change token constructed to precisely represent the delta; that change token is then "pushed" through the RETE for updating the network to reflect the change(s) that have occurred because of the WME change. Each time a change token is pushed (processed) through a RETE and is matched with patterns in a RETE constitutes a pattern match operation. Updating each join node for a delta or change token input may require calculating input arguments for the pattern tests from WME values stored at predecessor memory nodes. This calculation can be time consuming; therefore, it is desired to reduce such calculations without affecting accuracy of the pattern matching operations.
The RETE consists of alpha and beta portions. The alpha portions usually have no memory nodes, i.e. nodes wherein partial pattern matching results are stored; in contrast the beta portion includes such memory nodes and other nodes as well, such as join nodes which may include a plurality of tests involving a multiplicity of argument values. Intermediate the alpha and beta portions are alpha distribution nodes, all of which are memory nodes which store the partial patter matching results generated in the alpha portion. The RETE is updated by so-called change tokens. Each change token has an informational content showing the change in information (the delta) in the RETE system resulting from a new or changed WME or changes resulting from a deleted WME. Such change tokens are pushed through the alpha portion for creating partial match results to be stored in the alpha distribution nodes. Change tokens are then pushed from the alpha distribution nodes into the beta portion.
In the beta portion, each of the join nodes can have two inputs; a left hand sided input (LHS) input and a right hand sided input (RHS). A change token may arrive at either of the two inputs. A join node may include a multiplicity of pattern matching tests. When a token arrives at one input (either LHS or RHS), these tests may require plural test iterations for each change token; i.e. each test may have man test operations when the opposite memory has a large number of partial match tokens. These tests may be thought of as having two parts; a fist part which obtains the arguments for the tests and a second part which performs the test. For many applications, a majority of the time involved in performing a test is in obtaining the arguments; often, the test itself is simple, such as comparing two patterns for identity or equality. Such calculations lower RETE performance. This lowered performance is particularly notable when the nodes have a large number of tests to be performed. It is desired to reduce the execution time of pattern-matching networks of all types, and more particularly reduce time required in the beta portions of the RETE networks.
As known in the art, the outputs of the memory nodes represent an update status of the RETE; the memory node contents include partial match tokens and can be an input to a next successor node as an "opposite memory". The change token is compared with specified partial match tokens in the opposite memory. Such opposite memory is the memory of an immediate predecessor node on the "opposite" side of the node receiving the change token. This matching uses two kinds of information. A first kind of information describes pattern tests including a type of test function to call, specifications of the test arguments and information describing partially matched WME data element tokens. This first kind of information is computed when the RETE structure is built from specified patterns. A second kind of information is computed as WMEs are created, modified or deleted which cause WME change tokens to be pushed through the RETE. It is to be understood that accesses to all information follow usual programming procedures and that the matching operations are usual programming effected comparisons. As one example, a single join or a match node each could utilize 100, 1000 or more values in a single test; such values are scanned for effecting comparisons looking for a match with a change token being pushed through the network. Each such node may have many of such tests.